1. Field of the Invention
This disclosure relates to a method and corresponding computer-implemented system of detecting skew angle in skewed printed Arabic documents that are either printed or scanned and aligning to its correct horizontal position.
2. Description of the Related Art
The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventor, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present invention.
Performing skew correction has become an important process that professionals and individuals have come to rely on when scanning, printing and photocopying documents. It can be difficult to obtain a scan or a photocopy of a document that is not skewed having the horizontal text aligned correctly. Skewed text can make a document look messy and unprofessional amongst other things. Therefore the value of having an automatic skew detector and corrector for professional applications can be appreciated when confronted with this issue.
An old but comprehensive survey on skew detection techniques can be found in [J. J. Hull, Document image skew detection: Survey and annotated bibliography. World Scientific, 1998—incorporated herein by reference]. Commonly used techniques for skew detection are based on Hough transformation [S. C. Hinds, J. L. Fisher, and D. P. D'Amato, “A document skew detection method using run-length encoding and the Hough transform,” in Pattern Recognition, 1990. Proceedings, 10th International Conference on, 1990, vol. 1, pp. 464-468.—incorporated herein by reference], principal component analysis, projection profiles [W. Postl, “Detection of linear oblique structures and skew scan in digitized documents,” in Proc. 8th Int. Conf. on Pattern Recognition, 1986, pp. 687-689; and D. S. Bloomberg and G. E. Kopec, “Method and apparatus for identification and correction of document skew,” U.S. Pat. No. 5,187,753 1993—incorporated herein by reference], and connected component analysis [L. O'Gorman, “The document spectrum for page layout analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1162-1173, 1993; and Drivas and A. Amin, “Page segmentation and classification utilising a bottom-up approach,” in Document Analysis and Recognition, 1995. Proceedings of the Third International Conference on, 1995, vol. 2, pp. 610-614 vol. 2.—incorporated herein by reference].
Baird's presented an algorithm for skew detection based on projection profile [K. S. Baird, “Anatomy of a versatile page reader,” Proceedings of the IEEE, vol. 80, no. 7, pp. 1059-1065, July 1992.—incorporated herein by reference]. The midpoints of the bottom of each connected component in the document are projected perpendicular to projection angles. The characteristic shape of the peak was located first followed by fitting the slopes with approximating functions based on iterative non-linear separable least squares fitting algorithm. The method was stated to work on variety of documents having different layouts (multiple columns, multiple fonts and font sizes, sparse tables, and with variable line spacing). The technique works best for skew angle within ±15.0° as stated by the author and thus may not work effectively for documents having larger skews. Le et al. algorithm for skew detection is based on connected component analysis and Hough transformation [D. S. Le, G. R. Thoma, and H. Wechsler, “Automated page orientation and skew angle detection for binary document images,” Pattern Recognition, vol. 27, no. 10, pp. 1325-1344, 1994.—incorporated herein by reference]. Hough transformation is applied on the pixels of the last black runs of each connected component. The maxima from the Hough accumulator array identify the skew angle. The technique was successfully applied to thousands of images of a large image database with accuracy of about 0.50 degrees. Akiyama and Hagita presented a skew detection technique based on projection profiles [T. Akiyama and N. Hagita, “Automated entry system for printed documents,” Pattern recognition, vol. 23, no. 11, pp. 1141-1154, 1990.—incorporated herein by reference]. The page image is divided into columns and projection profiles are calculated for each one of them. A peak in the projection profiles implies a text line. The skew angle is calculated by finding the arctangent of the shift between the adjoining projection profiles. It is an efficient technique in terms of computation time. The algorithm can work only on regular text documents which does not contain non-text regions. Moreover it may not work effectively for large skews when the projection profiles overlaps too much. Singh et al. [C. Singh, N. Bhatia, and A. Kaur, “Hough transform based fast skew detection and accurate skew correction methods,” Pattern Recognition, vol. 41, no. 12, pp. 3528-3546, 2008.—incorporated herein by reference] presented an algorithm for skew detection based on Hough transform. The technique addresses the issues related to using Hough transformation due to its space and time complexities. The speed of skew detection was improved by using a preprocessing stage where the image pixels were reduced using a modified form of Block Adjacency Graph (BAG). Next it employs the Hough transform for skew detection and finally corrects the skew using different rotation algorithms proposed. It is as an enhancement of the original algorithm presented in [H. K. Kwag, S. H. Kim, S. H. Jeong, and G. S. Lee, “Efficient skew estimation and correction algorithm for document images,” Image and Vision Computing, vol. 20, no. 1, pp. 25-35, 2002.—incorporated herein by reference].
Shatnawi and Omar [M. An-Shatnawi and K. Omar, “Skew Detection and Correction Technique for Arabic Document Images Based on Centre of Gravity,” Journal of Computer Science, vol. 5, no. 5, pp. 363-368, 2009—incorporated herein by reference] proposed an algorithm for skew correction of Arabic documents. In this algorithm the complete text block is inscribed in a polygon. The angle between the center of gravity (COG) of the polygon and an ideal horizontal origin is calculated as the document skew angle. The technique will work in text-only documents. Moreover it is not clear if and how the algorithm works on document images having more than one and non-uniform text blocks.
Sarfaraz and Rasheed [M. Sarfraz and Z. Rasheed, “Skew Estimation and Correction of Text Using Bounding Box,” in Computer Graphics, Imaging and Visualisation, 2008. CGIV '08. Fifth International Conference on, 2008, pp. 259-264.—incorporated herein by reference] presented a technique for skew estimation and correction using bounding box technique. Bounding Box technique finds the extreme corners of text image (using projection profiles). The algorithm next calculates the Euclidean distance between these points. The slopes of adjacent sides of the bounding box are calculated to estimate the skew angle. The algorithm here too will work on text-only documents. Sarfaraz et al. [M. Sarfraz, S. A. Mahmoud, and Z. Rasheed, “On Skew Estimation and Correction of Text,” in Computer Graphics, Imaging and Visualisation, 2007. CGIV '07, 2007, pp. 308-313—incorporated herein by reference] presented two different algorithms for skew detection. The first algorithm is based on finding peaks and valleys using projection profiles. The input image is bisected initially into right and left halves. Peaks and valleys for each half of the image is analyzed (using projection profile) and histograms are plotted. Lines are projected between the starting and ending points by analyzing the consecutive valleys on each segment of the image. Finally the skew angle is calculated using the trigonometric ratios. It seems the algorithm may work on very restricted types of documents having text-only regions. It is not clear if the algorithm will work on documents having multiple non-uniform text blocks. The second algorithm is based on connected component analysis and mathematical morphological operations. It is based on the observation (also a pre-condition for the algorithm) that the distance between adjacent words on different lines will be much greater than the distance between adjacent words within a line. Based on this observation, all words in a line are made as one single object or blob using mathematical morphological operations (like dilation). The skew angle is estimated by calculating the orientation of the line (the major axis of the blob is treated as the line).